Obeleži sve kategorije koje odgovaraju problemu

Ред

Ред представља колекцију података у коју се подаци додају по FIFO (енгл. first-in-first-out) принципу – елемент се увек узима са почетка, а додаје на крај реда.

У језику C++ ред се реализује класом queue<T> где T представља тип елемената на стеку. За њено коришћењем потребно је укључити заглавље <queue>. Подржане су следеће методе (све сложености \(O(1)\)):

• push - поставља дати елемент на крај реда
• pop - скида елемент са почетка реда (под претпоставком да ред није празан). Нагласимо да је ова метода типа void и да не враћа уклоњени елемент.
• front - очитава елемент на почетку реда (под претпоставком да ред није празан)
• empty - проверава да ли је ред празан
• size - враћа број елемената у реду

Ако се у реду чувају уређени парови или n-торке, тада се уместо методе push, може користити метода emplace, којој се само редом наводе елементи пара тј. n-торке (није потребно посебно позивати функцију за креирање пара тј. n-торке, што је неопходно када се користи push).

Ред у језику C++ је заправо само адаптер око неке колекције података (подразумевано реда са два краја) који корисника тера да поштује правила приступа реду и спречава да направи операцију која над редом није допуштена (попут приступа неком елементу који није на почетку).

Ред са два краја

Уопштење представља ред са два краја који допушта да се елементи и додају и узимају са било ког краја реда (та структура података заправо комбинује и функционалност стека и функционалност реда).

У језику C++ могуће је користити структуру deque<T>. За њено коришћење потребно је укључити заглавље <deque>. Подржане су следеће операције (све сложености \(O(1)\)).

• push_front - додавање елемента на почетак
• push_back - додавање елемента на крај
• front - читање елемента са почетка (под претпоставком да ред није празан)
• back - читање елемента са краја (под претпоставком да ред није празан)
• pop_front - уклањање елемента са почетка (под претпоставком да ред није празан). Нагласимо да је ова метода типа void и да не враћа уклоњени елемент.
• pop_back - уклањање елемента са краја (под претпоставком да ред није празан). Нагласимо да је ова метода типа void и да не враћа уклоњени елемент.
• empty - провера да ли је ред празан
• size - број елемената у реду

Интересантно, захваљујући специфичном начину имплементације, ова структура података подржава и оператор индексног приступа којим се елемент на датој позицији може прочитати или изменити у времену \(O(1)\).

Ред

Ред представља колекцију података у коју се подаци додају по FIFO (енгл. first-in-first-out) принципу – елемент се увек узима са почетка, а додаје на крај реда.